1. Field of the Invention
The present invention relates to a method and apparatus for data clustering, especially regarding images, utilizing a novel fast, multiscale algorithm. More particularly, the present invention relates to a method and apparatus for image segmentation and boundary detection.
2. Description of the Prior Art
Data clustering is the task of inferring properties of large amounts of data. Clustering is obtained through a process of unsupervised learning in which the data is split into clusters, which reveal its inner structure. Methods are known which employ a large class of graph algorithms adapted to deal with the data clustering problem, and more particularly, the segmentation problem. The algorithms employed typically construct a graph in which the nodes represent the pixels in the image and arcs represent affinities (“couplings”) between nearby pixels. In these methods, the image is segmented by minimizing a cost associated with cutting the graph into sub-graphs. In the simpler version, the cost is the sum of the affinities across the cut. Other versions normalize this cost by dividing it by the overall area of the segments or by a measure derived from the affinities between nodes within the segments. Normalizing the cost of a cut prevents over-segmentation of the image. Attaining a globally optimal solution for normalized-cuts measures is known to be NP-hard even for planar graphs. Some variations of normalized-cuts measures can be found in polynomial time, but the runtime complexity of these methods is O(N2 log N), where N denotes the number of pixels in the image. Therefore, approximation methods are used. The most common approximation method uses spectral techniques to find a solution. These spectral methods are analogous to finding the principal modes of certain physical systems. With these methods, and exploiting the sparseness of the graph, a cut can be found in O(N3/2).